package com.ch;

/**
 * @author chenhong
 * @version 1.0.0
 * @ClassName 分发糖果.java
 * @Description TODO
 * @createTime 2020年12月24日 11:10:00
 */
public class 分发糖果 {
}

/**
 * 两次遍历，先左遍历，再右遍历
 */
class Solution135 {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];
        // 先左遍历，找到从左往右走，每个小朋友需要的最多糖果，如果i==0 或者评分i <= i-1，则left[i]=1
        // 否则left[i] = left[i-1] + 1;
        for (int i = 0; i < n; i++) {
            if (i > 0 && ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else {
                left[i] = 1;
            }
        }
        //然后从右向左遍历，最右的节点 n-1 right等于 1
        //或者当前节点 i <= i+1的 right等于1
        //否则当前节点 right++
        //然后比较从左边的left[i] 和 当前的 right ，取最大
        int right = 0, ret = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (i < n - 1 && ratings[i] > ratings[i + 1]) {
                right++;
            } else {
                right = 1;
            }
            ret += Math.max(left[i], right);
        }
        return ret;
    }
}

